import java.util.HashMap;
import java.util.Map;

public class HouseRobberIII {
    /**
     * 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为root。
     * 除了root之外，每栋房子有且只有一个“父“房子与之相连。
     * 一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
     * 给定二叉树的root。返回在不触动警报的情况下，小偷能够盗取的最高金额。
     * 链接：https://leetcode-cn.com/problems/house-robber-iii
     * @param root
     * @return
     */
    Map<TreeNode,Integer> f_map = new HashMap<TreeNode,Integer>();
    Map<TreeNode,Integer> g_map = new HashMap<TreeNode,Integer>();
    public int rob(TreeNode root) {

        dfs(root);
        return Math.max(f_map.getOrDefault(root,0),g_map.getOrDefault(root,0));

    }

    public void dfs(TreeNode treeNode){
        if (treeNode==null)
            return;
        dfs(treeNode.left);
        dfs(treeNode.right);
        f_map.put(treeNode,treeNode.val+g_map.getOrDefault(treeNode.left,0)+ g_map.getOrDefault(treeNode.right,0));
        g_map.put(treeNode,Math.max(f_map.getOrDefault(treeNode.right,0),g_map.getOrDefault(treeNode.right,0))+
                Math.max(f_map.getOrDefault(treeNode.left,0),g_map.getOrDefault(treeNode.left,0))
                );
    }
}
